package acm;

import java.util.Scanner;

public class 操作格子 {
    static Scanner in = new Scanner(System.in);
    static int n=in.nextInt();
    static int m=in.nextInt();
    static int[] a= new int[n+1];
    public static void main(String[] args){
        int p,x,y;
        for (int i=1;i<=n;i++){
            a[i]=in.nextInt();
        }
        for (int i=0;i<m;i++){
            p=in.nextInt();
            switch (p){
                case 1:
                    x=in.nextInt();
                    y=in.nextInt();
                    change(x,y);
                    break;
                case 2:
                    x=in.nextInt();
                    y=in.nextInt();
                    System.out.println(add(x,y));
                    break;
                case 3:
                    x=in.nextInt();
                    y=in.nextInt();
                    System.out.println(max(x,y));
                    break;
            }
        }
    }
    public static int max(int x,int y){
        int maxs=a[x];
        for (int i=x+1;i<=y;i++){
           if (a[i]>a[x]){
               maxs=a[i];
           }
        }
        return maxs;
    }
    public static void change(int x,int y){
        a[x]=y;
    }
    public static int add(int x,int y){
        int sum=0;
        for (int i=x;i<=y;i++){
            sum+=a[i];
        }
        return sum;
    }
}
